package week_03;

/**
 * 433. 最小基因变化
 * 一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T"中的任意一个。
 * <p>
 * 假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
 * <p>
 * 例如，基因序列由"AACCGGTT"变化至"AACCGGTA"即发生了一次基因变化。
 * <p>
 * 与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。
 * <p>
 * 现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，
 * 请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。
 * <p>
 * 注意：
 * <p>
 * 起始基因序列默认是合法的，但是它并不一定会出现在基因库中。
 * 如果一个起始基因序列需要多次变化，那么它每一次变化之后的基因序列都必须是合法的。
 * 假定起始基因序列与目标基因序列是不一样的。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * start: "AACCGGTT"
 * end:   "AACCGGTA"
 * bank: ["AACCGGTA"]
 * <p>
 * 返回值: 1
 * 示例 2：
 * <p>
 * start: "AACCGGTT"
 * end:   "AAACGGTA"
 * bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
 * <p>
 * 返回值: 2
 * 示例 3：
 * <p>
 * start: "AAAAACCC"
 * end:   "AACCCCCC"
 * bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
 * <p>
 * 返回值: 3
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-genetic-mutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MinMutationChange_test_433 {
    private int ans;
    private int opt;
    private String[] bank;
    private char[] muta = new char[]{'A', 'C', 'G', 'T'};

    public int minMutation(String start, String end, String[] bank) {
        ans = 0;
        opt = 0;
        this.bank = bank;
        findDfs(start.toCharArray(), end.toCharArray());
        return ans;
    }

    private void findDfs(char[] chars, char[] endChars) {
        // 不在bank中就停止
        if (!isInBank(chars)) return;
        // 在bank中且和target相等，更新最小步数；
        if (isEquals(chars, endChars)) {
            ans = Math.min(ans, opt);
            return;
        }
        //向其他三个基因和目标基因变换
        for (int i = 0; i < chars.length; i++) {
            for (int k = 0; k < 4; k++) {
                if (chars[i] != endChars[i]) {
                    if (chars[i] == muta[k]) continue;
                    chars[i] = muta[k];
                    opt++;
                    findDfs(chars, endChars);
                    opt--;
                    //chars[i];
                }
            }
        }

    }

    public boolean isEquals(char[] chars, char[] endChars) {
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != endChars[i]) return false;
        }
        return true;
    }

    public boolean isInBank(char[] chars) {
        for (String s : bank) {
            if (s.equals(String.copyValueOf(chars))) return true;
        }
        return false;
    }
}
